package com.ycz.algorithm.utils.graph;

import com.ycz.algorithm.utils.graph.adjacencylist.AdjacencyList;
import com.ycz.algorithm.utils.graph.adjacencylist.Vertex;

import java.util.*;

/**
 * @author yancz
 * @ClassName GraphUtil
 * @description: // 图的遍历操作
 * @date 2025-01-10 16:31:49
 * @version: 1.0
 */
public class GraphUtil {

    /*
     * @author yancz
     * @description // 广度优先遍历邻接表
     * @date 2025/1/10 16:33
     * @param graph 邻接表实现的图
     * @param start 开始的顶点
     * @return List<Vertex> 返回依次遍历的顶点序列
     */
    public static List<Vertex> graphBFS(AdjacencyList graph, Vertex start) {
        List<Vertex> res = new ArrayList<>(); // 存储遍历过的顶点序列
        Set<Vertex> visitedSet = new HashSet<>(); // 记录已访问的顶点
        visitedSet.add(start);
        // 队列用于实现BFS
        Queue<Vertex> queue = new LinkedList<>();
        queue.offer(start); // 开始顶点入队
        while (!queue.isEmpty()) { // 队列不为空时
            Vertex vertex = queue.poll(); // 队头出队
            res.add(vertex); // 记录该顶点
            Set<Vertex> neighboSet = graph.adjList.get(vertex); // 获取邻接表中与该顶点相邻的顶点
            for (Vertex v : neighboSet) {
                if (visitedSet.contains(v)) { // 如果已访问过该顶点，则不再访问
                    continue;
                }
                queue.offer(v);
                visitedSet.add(v);
            }
        }
        return res;
    }

    /*
     * @author yancz
     * @description // 深度优先遍历邻接表
     * @date 2025/1/24 10:25
     * @param graph 邻接表图
     * @param start 开始的顶点
     * @return List<Vertex> 顶点值序列
     */
    public static List<Vertex> graphDFS(AdjacencyList graph, Vertex start) {
        List<Vertex> res = new ArrayList<>();
        Set<Vertex> visitedSet = new HashSet<>();
        dfs(graph, visitedSet, res, start);
        return res;
    }

    /*
     * @author yancz
     * @description // TODO
     * @date 2025/1/24 10:42
     * @param graph 邻接表表
     * @param visitedSet 已访问的顶点集合
     * @param res 遍历的顶点序列
     * @param start 开始顶点
     * @return void
     */
    private static void dfs(AdjacencyList graph, Set<Vertex> visitedSet, List<Vertex> res, Vertex start) {
        res.add(start); // 记录访问顶点
        visitedSet.add(start); // 标记该顶点已被访问
        Set<Vertex> sets = graph.adjList.get(start);
        for (Vertex v : sets) {
            if (visitedSet.contains(v)) { // 若已访问过的顶点集合中包含当前节点，则跳过
                continue;
            }
            dfs(graph, visitedSet, res, v);
        }
    }

    public static void main(String[] args) {
        // 顶点实例化
        Vertex a = new Vertex(0);
        Vertex b = new Vertex(1);
        Vertex c = new Vertex(2);
        Vertex d = new Vertex(3);
        Vertex e = new Vertex(4);
        Vertex f = new Vertex(5);
        Vertex g = new Vertex(6);
        Vertex h = new Vertex(7);
        Vertex i = new Vertex(8);
        // 构建邻接表图
        Vertex[][] edges = {
                {a, b}, {a, d},   // 顶点0的边
                {b, a}, {b, c}, {b, e},   // 顶点1的边
                {c, b}, {c, f}, // 顶点2的边
                {d, a}, {d, e}, {d, g},   // 顶点3的边
                {e, b}, {e, d}, {e, f}, {e, h}, // 顶点4的边
                {f, c}, {f, e}, {f, i}, // 顶点5的边
                {g, d}, {g, h}, // 顶点6的边
                {h, e}, {h, g}, {h, i}, // 顶点7的边
                {i, f}, {i, h} // 顶点8的边
        };
        AdjacencyList adjacencyList = new AdjacencyList(edges);
        // 广度优先遍历
        List<Vertex> res = graphBFS(adjacencyList, a);
        System.out.println("广度优先遍历序列：");
        for (Vertex v : res) {
            System.out.print(v.val + "\t");
        }
        System.out.println();
        // 构建图
        Vertex[][] edges2 = {
                {a, b}, {b, c}, {c, f}, {f, e}, {f, g}, {a, d}
        };
        AdjacencyList adjacencyList2 = new AdjacencyList(edges2);
        List<Vertex> res2 = graphDFS(adjacencyList2, a);
        // 深度优先遍历
        System.out.println("深度优先遍历序列：");
        for (Vertex v : res2) {
            System.out.print(v.val + "\t");
        }
    }

}
